package Algorithms;

public class QuickSort  {
	
	private int[] arrayToSort;
	private int length;

	public void sort(int[] values) {
		// Check for empty or null array
		if (values ==null || values.length==0){
			return;
		}
		this.arrayToSort = values;
		length = values.length;
		quicksort(0, length - 1);
	}

	private void quicksort(int low, int high) {
		int i = low, j = high;
		// Get the pivot element from the middle of the list
		int pivot = arrayToSort[low + (high-low)/2];

		// Divide into two lists
		while (i <= j) {
			// If the current value from the left list is smaller then the pivot
			// element then get the next element from the left list
			while (arrayToSort[i] < pivot) {
				i++;
			}
			// If the current value from the right list is larger then the pivot
			// element then get the next element from the right list
			while (arrayToSort[j] > pivot) {
				j--;
			}

			// If we have found a values in the left list which is larger then
			// the pivot element and if we have found a value in the right list
			// which is smaller then the pivot element then we exchange the
			// values.
			// As we are done we can increase i and j
			if (i <= j) {
				exchange(i, j);
				i++;
				j--;
			}
		}
		// Recursion
		if (low < j)
			quicksort(low, j);
		if (i < high)
			quicksort(i, high);
	}

	private void exchange(int i, int j) {
		int temp = arrayToSort[i];
		arrayToSort[i] = arrayToSort[j];
		arrayToSort[j] = temp;
	}
	
	public void printRes(){
		for (int i = 0; i < arrayToSort.length; i++)
			System.out.println(arrayToSort[i]);
	}
}